package a00_LeetCode.Tree;

/**
 * @Author quan
 * @Description 翻转二叉树
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 * @Date 2023/3/24 19:39
 */

import java.util.Deque;
import java.util.LinkedList;

/**
 * 后序遍历：先递归的反转左树，再递归的反转右树，再交换两个树的位置
 */
public class Num226_invertTree {
  /*  public TreeNode invertTree(TreeNode root) {
        //(1)边界条件：树为空且只有一个根存在
        if(root==null||root.left==null&&root.right==null){
            return root;
        }
        //(2)否则：先递归的反转左子树
        root.left = invertTree(root.left);
        //再递归的反转右子树
        root.right = invertTree(root.right);
        //(3)交换反转后的左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }*/
    /**
     * 层序遍历方式
     */
    public TreeNode invertTree(TreeNode root) {
        //(1)边界条件：树为空且只有一个根存在
        if(root==null||root.left==null&&root.right==null){
            return root;
        }
        //层序遍历需要队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        while (!deque.isEmpty()){
            TreeNode node = deque.poll();
            if(node.left != null){
                deque.offer(node.left);
            }
            if(node.right != null){
                deque.offer(node.right);
            }
            swap(node);
        }
        return root;
    }
    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
